package 单周赛.history;

import java.util.*;

/**
 *
 */
public class 第329场单周赛 {

    public static void main(String[] args) {

        System.out.println(alternateDigitSum(521));

        sortTheStudents(new int[][]{{10, 6, 9, 1}, {7, 5, 11, 2}, {4, 8, 3, 15}}, 2);

        System.out.println(minCost(new int[]{1, 2, 1, 2, 1}, 5));

    }

    public static int alternateDigitSum(int n) {
        int sum = 0;
        List<Integer> list = new ArrayList<>();

        while (n > 0) {
            list.add(n % 10);
            n /= 10;
        }

        boolean flag = false;
        for (int i = list.size() - 1; i >= 0; i--) {
            if (flag) {
                sum -= list.get(i);
            } else {
                sum += list.get(i);
            }

            if (flag) {
                flag = false;
            } else {
                flag = true;
            }
        }
        return sum;
    }

    /**
     * 哈希表+排序
     */
    public static int[][] sortTheStudents(int[][] score, int k) {
        Map<Integer, int[]> map = new HashMap<>();
        int[] temp = new int[score.length];
        for (int i = 0; i < score.length; i++) {
            temp[i] = score[i][k];
            map.put(temp[i], score[i]);
        }

        Arrays.sort(temp);

        for (int i = score.length - 1; i >= 0; i--) {
            score[i] = map.get(temp[score.length - 1 - i]);
        }

        return score;
    }

    /**
     * 贪心思想+分类讨论
     * 分析：
     * 只要存在一个 1 就可以将任意一个 0 变成 1
     * 如果有 n 个 1 ，那么可以将任意 n-1 个 1 变成 0
     * 1，如果 s 中没有 1 ，那么永远不可能有 1，此时
     * target 中有 1 的话，永远不能满足条件
     * 2，如果 target 中没有 1 ，s 中有 1 的话，
     * s中始终最后会剩下一个 1，永远不能满足条件
     */
    public boolean makeStringsEqual(String s, String target) {
        int sOne = 0, tOne = 0;
        for (char c : s.toCharArray()) {
            if (c - '0' == 1) {
                sOne++;
            }
        }
        for (char c : target.toCharArray()) {
            if (c - '0' == 1) {
                tOne++;
            }
        }

        if (sOne == 0 && tOne > 0) {
            return false;
        }

        if (tOne == 0 && sOne > 0) {
            return false;
        }
        return true;
    }

    /**
     * 动态规划
     * 1，子问题：
     * dp[i] 表示在 nums[0,i] 中拆分子数组的最小代价
     * 2，初始值分析：
     * dp[0] = k ，此时只有一个数，可以去除，负数为 k
     * 3，状态转移方程：
     * dp[i] = dp[j-1] + cost(j,i)
     * cost(j,i) 表示将 [j,i] 拆分为一个子数组的代价
     * 注意：
     * 计算代价可以记录每个数字出现的次数
     * 当前数字出现第二次时 ，代价 +2
     * > 2 时，代价 +1
     * 来降低时间复杂度
     */
    public static int minCost(int[] nums, int k) {
        int[] dp = new int[nums.length];
        dp[0] = k;

        for (int i = 1; i < nums.length; i++) {
            Map<Integer, Integer> map = new HashMap<>();

            int addCnt = 0;
            for (int j = i; j >= 0; j--) {
                int curCost = k;
                if (map.getOrDefault(nums[j], 0) == 1) {
                    addCnt += 2;
                } else if (map.getOrDefault(nums[j], 0) > 1) {
                    addCnt++;
                }
                map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);

                curCost += addCnt;

                if (dp[i] == 0) {
                    dp[i] = ((j - 1) >= 0 ? dp[j - 1] : 0) + curCost;
                } else {
                    dp[i] = Math.min(dp[i], ((j - 1) >= 0 ? dp[j - 1] : 0) + curCost);
                }
            }
        }

        return dp[dp.length - 1];
    }
}
